home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_high.lha / LEDA-3.1c-high / man / segment_set.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  3.8 KB  |  97 lines
  1.  
  2.  
  3. {\magonebf  6.5 Sets of parallel segments (segment\_set)}
  4.  
  5. \decl segment\_set I
  6.  
  7. {\bf 1. Definition}
  8.  
  9. An instance $S$ of the parameterized data type \name\ is a 
  10. collection of items ($seg\_item$). Every item in $S$ contains as key a 
  11. line segment with a fixed direction $\alpha$ (see data type segment) and 
  12. an information from data type $I$, called the information type of $S$. 
  13. $\alpha$ is called the orientation of $S$. We use $<s,i>$ to denote the 
  14. item with segment $s$ and information $i$. For each segment $s$ there is 
  15. at most one item $<s,i> \in S$.
  16.  
  17.  
  18. \bigskip
  19. {\bf 2. Creation}
  20.  
  21. a) \create S (double\ \alpha)
  22.  
  23. b) \create S {}
  24.  
  25. creates an empty instance \var\ of type \name\ with orientation $\alpha$.
  26. Variant b) creates a segment set of orientation zero, i.e., for horizontal 
  27. segments.
  28.  
  29.  
  30.  
  31. \bigskip
  32. {\bf 3. Operations}
  33.  
  34. \+\cleartabs & \hskip 3truecm & \hskip 5.5truecm &\cr
  35. \+\op segment         key {seg\_item\ it} 
  36.                                  {returns the segment of item $it$.}
  37. \+\nop                           {\precond $it$ is an item in \var.}
  38. \smallskip
  39. \+\op I               inf {seg\_item\ it} 
  40.                                  {returns the information of item $it$.}
  41. \+\nop                           {\precond $it$ is an item in \var.}
  42. \smallskip
  43. \+\op seg\_item       insert {segment\ s,\ I\ i}
  44.                                  {associates the information $i$ with segment}
  45. \+\nop                           {$s$. If there is an item $<s,j>$ in \var }
  46. \+\nop                           {then $j$ is replaced by $i$, else a new item }
  47. \+\nop                           {$<s,i>$ is added to $S$. In both cases the}
  48. \+\nop                           {item is returned.}
  49. \smallskip
  50. \+\op ps\_item        lookup {segment\ s} 
  51.                                  {returns the item with segment $s$ (nil}
  52. \+\nop                           {if no such item exists in \var).}
  53. \smallskip
  54. \+\op list\<seg\_item\> intersection {segment\ q}
  55.                                  {returns all items $<s,i>\ \in\ S$ with}
  56. \+\nop                           {$s \cap q \neq \emptyset$. \precond $q$ is}
  57. \+\nop                           {orthogonal to the segments in \var.}
  58. \smallskip
  59. \+\op list\<seg\_item\> intersection {line\ l}
  60.                                  {returns all items $<s,i>\ \in\ S$ with}
  61. \+\nop                           {$s \cap l \neq \emptyset$. \precond $l$ is}
  62. \+\nop                           {orthogonal to the segments in \var.}
  63. \smallskip
  64. \+\op void            del {segment\ s}         
  65.                                  {deletes the item with segment $s$}
  66. \+\nop                           {from \var.}
  67. \smallskip
  68. \+\op void            del\_item {seg\_item it}   
  69.                                  {removes item $it$ from \var.}
  70. \+\nop                           {\precond $it$ is an item in \var.}
  71. \smallskip
  72. \+\op void            change\_inf 
  73.                                  {seg\_item\ it,\ I\ i}  {}
  74. \+\nop                           {makes $i$ the information of item $it$.}
  75. \+\nop                           {\precond $it$ is an item in \var.}
  76. \smallskip
  77. \+\op void            clear {}           
  78.                                  {makes \var\ the empty segment\_set.}
  79. \smallskip 
  80. \+\op bool            empty {}           
  81.                                  {returns true iff \var\ is empty.}
  82. \smallskip 
  83. \+\op int             size {}            
  84.                                  {returns the size of \var.}
  85.  
  86.  
  87.  
  88. \bigskip
  89. {\bf 4. Implementation}
  90.  
  91. Segment sets are implemented by dynamic segment trees based on BB[$\alpha$]
  92. trees ([Wi85, Lu78]) trees. Operations key, inf, change\_inf, empty, and size 
  93. take time $O(1)$, insert, lookup, del, and del\_item take time $O(\log^2 n)$ 
  94. and an intersection operation takes time $O(k + \log^2 n)$, where $k$ is the 
  95. size of the returned list. Here $n$ is the current size of the set. The space 
  96. requirement is $O(n\log n)$.
  97.